package huawei.window;

/**
 * https://leetcode-cn.com/problems/get-equal-substrings-within-budget/
 */
public class J1208 {
    public static void main(String[] args){
        System.out.println(equalSubstring( "abcd",  "bcdf", 3));//3
        System.out.println(equalSubstring( "abcd",  "cdef", 3));//1
        System.out.println(equalSubstring( "abcd",  "acde", 0));//1
    }
    public static int equalSubstring(String s, String t, int maxCost) {
        /**
         * 滑动窗口,right递增找最长字串,触发>maxCost left++缩小窗口,
         * 优化,缓存char差值计算
         */
        int left=0;
        int right=0;
        int maxLen =0;
        int curCost=0;
        int[] diff =new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            diff[i]=Math.abs(s.charAt(i)-t.charAt(i));
        }
        while (right<s.length()){
            curCost+=diff[right];
            while (curCost>maxCost){
                curCost-=diff[left];
                left++;
            }
            maxLen=Math.max(maxLen,right-left+1);
            right++;
        }
        return maxLen;
    }
}
